import numpy as np
import copy
import random
import matplotlib.pyplot as plt

path = "./resources/data.txt"
data = []


def loadData(path):
    with open(path, 'r') as fp:
        for line in fp.readlines():
            tempList = line.strip().split(',')
            data.append([float(tempList[1]), float(tempList[2])])
    fp.close()


def showData(clustering, k):
    color = []
    size = [25, 100]
    index = -1
    noiseSample = copy.deepcopy(data)
    plt.title('DBSCAN')
    plt.xlabel('density')
    plt.ylabel('sweetness')
    for i in range(k):
        color.extend(["#" + ''.join([random.choice('0123456789ABCDEF') for j in range(6)])])
    for i in range(len(clustering)):
        for j in range(len(clustering[i])):
            for m in range(len(data)):
                if (data[m] == clustering[i][j]).all():
                    noiseSample.remove(data[m])
                    if 8 <= m <= 20:
                        index = 0
                    else:
                        index = 1
                    break

            plt.scatter(clustering[i][j][0], clustering[i][j][1], c=color[i], s=size[index])
    if len(noiseSample):
        print(len(noiseSample))
        for i in range(len(noiseSample)):
            plt.scatter(noiseSample[i][0], noiseSample[i][1], s=50, marker='*', c='black')

    plt.show()


def DBSCAN(maxDistance, minPts):
    data_array = np.array(data)
    sampleNumber = len(data_array)
    neighborhood = {}
    coreObject = []
    clusteringIndex = {}

    for i in range(sampleNumber):
        neighborhood[i] = []
    # 计算邻域，并确定核心对象集合
    for i in range(sampleNumber):
        for j in range(sampleNumber):
            dist = np.linalg.norm(data_array[i]-data_array[j])
            if dist <= maxDistance:
                neighborhood[i].append(j)
    for i in range(sampleNumber):
        if len(neighborhood[i]) >= minPts:
            coreObject.append(i)

    # 初始化簇类数，以及未访问样本集合
    k = 0
    queue = []
    notVisit = []
    for i in range(sampleNumber):
        notVisit.append(i)

    while len(coreObject):
        notVisitOld = copy.deepcopy(notVisit)
        randomIndex = np.random.randint(len(coreObject))
        queue.clear()
        queue.append(coreObject[randomIndex])
        notVisit.remove(coreObject[randomIndex])

        while len(queue):
            q = queue[0]
            queue.remove(q)
            if len(neighborhood[q]) >= minPts:
                delete = [value for value in neighborhood[q] if value in notVisit]
                queue.extend(delete)
                for i in range(len(delete)):
                    notVisit.remove(delete[i])
        # 簇数加1
        k += 1
        clusteringIndex[k-1] = []
        clusteringIndex[k-1].extend([value for value in notVisitOld if value not in notVisit])

        # 更新核心对象集
        coreObject = [value for value in coreObject if value not in clusteringIndex[k-1]]

    return clusteringIndex, k


if __name__ == '__main__':
    loadData(path)
    clusteringIndex, k = DBSCAN(0.11, 5)
    clustering = {}
    for i in range(len(clusteringIndex)):
        clustering[i] = []
        for j in range(len(clusteringIndex[i])):
            clustering[i].append(np.array(data[clusteringIndex[i][j]]))

    print(clusteringIndex)
    print(clustering)
    showData(clustering, k)
